yupsung Computer Science blog

03_6 : Anomaly Detection : Auto-Encoder, 1-SVM, SVDD MoG와 같은 밀도기반 방법론들은 특정 객체가 정상범주에 속할 확률을 구했다. 반면 Support vector 기반 방법론들은 normal과 abnormal을 구분하는 분류경계면을 찾는다. 이번 글에서는 Support vector 기반의 Anomaly detection 방법 중 one-class SVM과 SVDD를 알아보자. One-class Support Vector Machine (1-SVM, OCSVM) 1-SVM의 목표는 Data를 feature space로 mapping 한 뒤, 분류경계면을 통해 mapping된 Data 중 normal data들이 원점으로부터 최대한 멀어지게 만드는 것이다. 위 그림에서 파란색 분류경계면이 (+1) normal data들을 구분하는 것을 확인할 수 있다. 이 목표를 수식화 한 Optimization problem부터 살펴보자. Optimization Problem $$\min_{\textbf{w}}\;\;\;\frac{1}{2}||\textbf{w}||^2 + \frac{1}{\nu l} \sum_{i=1}^l \xi_i - \rho$$ $$s.t.\;\;\;\textbf{w}\cdot \Phi (x_i) \geq \rho - \xi_i\;\;\;\;(i=1,2,\cdots,l),\;\;\xi_i\geq 0$$ $\frac{1}{2}||\textbf{w}||^2$ term은 SVR과 같이 $x$의 변화에 따른 변동이 크지 않도록 Regularization을 하는 term이다. $\rho$는 위 그림에서 주황 직선을 나타내는데, 원점과 분류경계면 Hyperplane과의 거리를 나타낸다. 이 값을 뺌으로써 최소화 문제를 만족하는 최적해일때 $\rho$가 최대가 되도록 한다. (원점에서 Hyperplane이 최대한 멀어지게 만든다) $\frac{1}{\nu l} \sum_{i=1}^l \xi_i$ term은 제약식에 따라 Hyp

03_6 : Anomaly Detection : Auto-Encoder, 1-SVM, SVDD Auto encoder 자체는 다양한 분야에 활용되는 모델이다. 이 글에서는 간단하게 어떤식으로 이상치 탐지에 이용되는지 알아볼 것이다. Auto Encoder (Auto-Associative Neural Network) 이미지를 처리하는 경우 Convolutional Auto Encoder를, 시계열이나 자연어와 같은 데이터를 처리하는 경우 RNN 기반의 Auto Encoder를 사용하는 등 다양한 응용이 있다. 하지만 이 글에서는 가장 기본적인 Feed-forward neural network에서 Auto Encoder를 이해해보자. Auto Encoder의 목적은 입력으로 주어진 data를 출력으로 최대한 원본에 가깝게 reproduce 하는 것이다. 목적함수인 Loss function을 살펴보자. Loss function $$l(f(x)) = \frac{1}{2}\sum_k(\hat{x}_k-x_k)^2$$ 입력값 $x_k$와 reproduce 한 $\hat{x}_k$의 차이가 loss function이다. Encoder $$h(x) = g(a(x)) = sigmoid(b+Wx)$$ activation function으로 Sigmoid 함수를 사용한 예시이다. 입력 $x\in R^D$를 $h(x)\in R^d$로 인코딩한다. 이때 반드시 $d<D$이어야 한다. 왜냐하면 인코딩 과정에서 정보의 축약(손실)이 일어나야지만 입력 data의 특징을 잘 보존하는 hidden layer를 학습할 것이고, 이를 통해 이상치 탐지를 할 수 있기 때문이다. (이후에 좀더 자세히 알아보자) + hidden layer를 latent vector라고 부르기도 한다. Decode $$\hat{x} = o(\hat{a}(x)) = sigmoid(c+W^*h(x))$$ Encoding된 $h(x)$를 다시 원래 차원의 data $\hat{x}$로 복원하는 과정이다. 여기서 $W^

 03_2 : Anomaly Detection : (Mixture of) Gaussian Density Estimation 이전까지 normal data가 하나의 가우시안 분포로 부터 생성된다고 가정하였다. 하지만 하나의 가우시안만을 사용하는 것은 너무 엄격하다.( Strong model : uni-modal and convex ) 때문에 여러개의 가우시안 분포의 혼합( multi-modal )을 사용하여 설명하려고 한다. Mixture of Gaussian (MoG) Density Estimation Mixture of Gaussian(MoG)는 여러개의 가우시안 분포의 선형 결합으로 이루어진다. 덕분에 이전의 하나의 가우시안을 사용하는 경우보다 더 bias가 적게 추정이 가능하다. 하지만 좀 더 많은 Training data를 필요로 한다. $$f(x) = w_1N(\mu_1,\sigma_1^2) + w_2N(\mu_2,\sigma_2^2) + w_3N(\mu_3,\sigma_3^2)$$ 이전의 방법에서는 $\mu$와 $\sigma$ 2개의 미지수를 추정하면 되었지만, $K$개의 가우시안을 혼합하는 MoG의 경우에는 각 가우시안 마다 $w_i,\,\mu_i,\,\sigma_i$ 3개씩 총 $3K$개의 미지수, 그리고 몇개의 가우시안을 사용할지 $K$까지 학습을 통해 추정해야 한다. Components of MoG Probability of an instance belonging to the normal class $$p(x|\lambda) = \sum_{m=1}^M w_m g(x|\mu_m,\Sigma_m)$$ $$\lambda = \{w_m,\mu_m,\Sigma_m\},\;\;\;\;\;m=1,\cdots,M$$ Distribution of each Gaussian model $$g(x|\mu_m,\Sigma_m) = \frac{1}{(2\pi)^{d/2}|\Sigma_m|^{1/2}}\exp{\big[\frac{1}{2}(x-\mu_m)^T\Sigma

03_2 : Anomaly Detection : (Mixture of) Gaussian Density Estimation Density-based Novelty Detection 밀도 기반의 이상치 탐지 방법의 목적은 주어진 data를 기반으로 normal data의 분포를 추정하고, 추정한 분포를 사용하여 새로운 data가 주어졌을 때 발생할 확률을 구할 수 있다. 만약 발생 확률이 높다면 Normal data라고 판별하고, 낮다면 Abnormal data라고 판별한다. 만약 3이 input data로 주어진다면 추정한 가우시안 분포에 높은 확률 분포임으로 normal data라고 판별할 것이다. 하지만 -5가 input data로 주어진다면 가우시안 분포에서 낮은 확률 분포임으로 abnormal data라고 판별할 것이다. 여기서 주의할 점은 주어진 data가 가우시안 분포인지 아닌지를 모른다는 점이다. 때문에 이 방법을 사용하기 전에 적합한 data인지 판단하고 사용하어야 한다. Density-based Novelty(Abnormal) Detection 방법은 여러 종류가 있다. 먼저 전체 data가 하나의 가우시안 분포로부터 생성되었다는 가정하에 하나의 가우시안 분포를 추정하는 Gaussian Density Estimation이 있다. 즉 전체 Modal의 수가 1개이다. 두번째는 여러개의 가우시안 분포의 합성으로 이루어진 분포로부터 생성되었다는 가정하에 여러개의 가우시안 분포를 추정하는 Mixture of Gaussian Density Estimation이 있다. 이 경우 Modal의 수가 $1\leq (Number\;of\;modals)\leq (Number\;of\;instances)$를 만족한다. 세번째는 두번째 경우가 극한으로 표현한 경우이다. 모든 각 객체가 각 가우시안 분포의 중심이라 가정하고 이로부터 객체의 수 만큼의 가우시안 분포를 추정하는 방법이다. 이번에 알아볼 것은 Gaussian Density Estimation과 Mixture

03_1 : Anomaly Detection : Overview 이번에 알아볼 Anomaly Detection은 Data를 기반으로 다른 패턴, 특성을 보이는 객체를 찾아내는 방법이다. 이에 앞서 앞에서 지금까지 공부했던 Machine learning을 지도학습과 비지도학습으로 분류해보자.  Machine Learning 정의된 task T 가 있고, 성능을 측정할 수 있는 방법 P 가 있을 때 경험(Data) E 로부터 성능이 향상되는 컴퓨터 프로그램을  학습(Learn) 한다고 지칭한다. Machine Learning 은 이러한 조건을 만족한다. Machine learnnig은 주어진 Data의 특징에 따라 크게 두가지로 분류한다. Supervised learning 주어진 Data에 Target value (Y)를 알고있다. 주어진 Data (X, Y)를 사용하여, X와 Y사이의 관계, 이를 표현 가능한 함수 $Y=f(X)$를 알아내는 것이 목표이다. 지금까지 공부했던 Classification, Regression등이 여기에 해당한다. Unsupervised learning 주어진 Data에 Target value (Y)가 주어지지 않는다. 하지만 Data (X) 자체가 가지고 있는 특징$f(X)$를 알아내는 것이 목표이다. 주어진 Data (X)를 사용하여, 각각의 객체들의 밀도를 추정하거나, 객체들의 군집을 찾거나 변수들 간의 연관성을 유추한다. Anomaly Detection (이상치 탐지) Anomaly는 두가지 관점에서 정의된다. 데이터 생성 메터니즘 " Observations that deviate so much from other observations as to arouse suspicious that they were generated by a different mechanism (Hawkins, 1980) " 일반적인 데이터와 다른 메커니즘으로 발생한 data를 anomaly라고 한다. 데이터 분포 (밀도) "